#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:


    int ret = 0;
    vector<int> tmp;

    void MergeSort(vector<int>& record, int begin, int end)
    {
        if (begin >= end) return;

        int mid = (begin + end) / 2;
        MergeSort(record, begin, mid);
        MergeSort(record, mid + 1, end);

        int start1 = begin, end1 = mid;
        int start2 = mid + 1, end2 = end;

        int k = begin;
        while (start1 <= end1 && start2 <= end2)
        {
            if (record[start1] > record[start2])
            {
                ret += (end2 - start2 + 1);
                tmp[k] = record[start1];
                start1++;
            }
            else
            {
                tmp[k] = record[start2];
                start2++;
            }
            k++;
        }

        while (start1 <= end1)
        {
            tmp[k] = record[start1];
            start1++;
            k++;
        }

        while (start2 <= end2)
        {
            tmp[k] = record[start2];
            start2++;
            k++;
        }

        for (int i = begin; i <= end; i++)
        {
            record[i] = tmp[i];
        }
    }

    int reversePairs(vector<int>& record)
    {
        tmp.resize(record.size());
        MergeSort(record, 0, record.size() - 1);
        return ret;
    }
};

int main()
{
	return 0;
}